// LeetCode 面试 Problem Nr. 02.06: 回文链表

/*
编写一个函数，检查输入的链表是否是回文的。

示例 1：
	输入： 1->2
	输出： false
示例 2：
	输入： 1->2->2->1
	输出： true

进阶：
	你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-linked-list-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

package main

import "github.com/saint-yellow/think-leetcode/ds"

type ListNode = ds.SinglyLinkedNode[int]

func isPalindrome(head *ListNode) bool {
	return method1(head)
}

func convert(node *ListNode) *ListNode {
	var previous *ListNode
	current	:= node
	for current != nil {
		next := current.Next
		current.Next = previous
		previous = current
		current = next
	}
	return previous
}

func method1(head *ListNode) bool {
	if head == nil || head.Next == nil {
		return true
	}

	slow, fast := head, head
	for fast.Next != nil && fast.Next.Next != nil {
		fast = fast.Next.Next
		slow = slow.Next
	}

	p1, p2 := head, slow.Next
	slow.Next = nil
	p2 = convert(p2)
	for p2 != nil {
		if p1.Val != p2.Val {
			return false
		}

		p1, p2 = p1.Next, p2.Next
	}

	return true
}

func method2(head *ListNode) bool {
	current := head
	stack := make([]int, 0)

	for current != nil {
		stack = append(stack, current.Val)
		current = current.Next
	}

	current = head
	for current != head {
		pop := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		if pop != current.Val {
			return false
		}
		current = current.Next
	}

	return true	
}